0% completed
Problem Statement
You are given the root of a binary tree. The level of its root node is 1, the level of its children is 2, and so on.
Return the level x where the sum of the values of all nodes is the highest. If there are multiple levels with the same maximum sum, return the smallest level number x.
Examples
Example 1:
- Input: root =
[1, 20, 3, 4, 5, null, 8]
- Expected Output:
2 - Explanation:
Level 1 has nodes:[1]with sum =1
Level 2 has nodes:[20, 3]with sum =20 + 3 = 23
Level 3 has nodes:[4, 5, 8]with sum =4 + 5 + 8 = 17
The maximum sum is23at level2.
Example 2:
- Input: root =
[10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]
- Expected Output:
3 - Explanation:
Level 1 has nodes:[10]with sum =10
Level 2 has nodes:[5, -3]with sum =5 - 3 = 2
Level 3 has nodes:[3, 2, 11]with sum =3 + 2 + 11 = 16
Level 4 has nodes:[3, -2, 1]with sum =3 - 2 + 1 = 2
The maximum sum is16at level3.
Example 3:
- Input: root =
[5, 6, 7, 8, null, null, 9, null, null, 10]
- Expected Output:
2 - Explanation:
Level 1 has nodes:[5]with sum =5
Level 2 has nodes:[6, 7]with sum =6 + 7 = 13
Level 3 has nodes:[8, 9]with sum =8 + 9 = 17
Level 4 has nodes:[10]with sum =10
The maximum sum is17at level3.
Constraints:
- The number of nodes in the tree is in the range [1, 104].
- -105 <= Node.val <= 105
Solution
To solve this problem, we will use a level-order traversal technique, also known as Breadth-First Search (BFS). This approach is suitable because it processes each level of the tree one at a time, allowing us to calculate the sum of node values at each level efficiently. By keeping track of the sum for every level, we can easily find the level with the maximum sum.
At each level, we will compute the sum of all node values and compare it with the maximum sum found so far. If the current level's sum is higher, we update our result to the current level. This way, we ensure that we get the smallest level x with the maximum sum in a single pass through the tree.
Step-by-step Algorithm
-
Initialization:
- If the root is
null, return0immediately since there are no levels in the tree. - Initialize a queue (
queue) to help in level-order traversal. Add the root node to the queue. - Set
maxSumto the smallest possible integer (Integer.MIN_VALUE) to store the maximum sum found so far. - Set
resultLevelto1to store the level number with the maximum sum. - Initialize
currentLevelto1to keep track of the current level of traversal.
- If the root is
-
Start Level-Order Traversal:
-
While the queue is not empty, perform the following steps:
-
Process Nodes at the Current Level:
-
Get the number of nodes at the current level by taking the size of the queue (
levelSize). -
Initialize
currentSumto0to store the sum of node values at the current level.
- Iterate Over All Nodes at the Current Level:
- For each node in the level (from
i = 0toi < levelSize), perform the following:-
Remove the front node from the queue and store it in a variable (
node). -
Add the value of the
nodetocurrentSum.
- Add Children of the Node to the Queue:
- If the left child of the
nodeis notnull, add it to the queue. - If the right child of the
nodeis notnull, add it to the queue.
- If the left child of the
-
- For each node in the level (from
-
-
Update Maximum Sum and Level:
- After processing all nodes at the current level:
- Compare
currentSumwithmaxSum. - If
currentSumis greater thanmaxSum, updatemaxSumtocurrentSumand setresultLeveltocurrentLevel.
- Compare
- After processing all nodes at the current level:
-
Move to Next Level:
- Increment
currentLevelby1.
- Increment
-
-
End of Traversal:
- When the queue is empty, it means all levels have been processed.
-
Return Result:
- Return
resultLevel, which contains the level with the maximum sum.
- Return
Algorithm Walkthrough
Let's walk through the algorithm using the input [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]:
-
Initial Setup:
maxSum=Integer.MIN_VALUE(a very small value).resultLevel=1.currentLevel=1.queue=[10](contains only the root).
-
Processing Level 1:
levelSize=1(only one node at level 1).currentSum=0.- Loop through all nodes at this level (
i = 0 to levelSize-1):- Dequeue node
10from the queue. - Add
10tocurrentSum:currentSum = 10. - Add left child
5to the queue. - Add right child
-3to the queue.
- Dequeue node
- After processing level 1:
currentSum=10.maxSumis updated to10because10 > Integer.MIN_VALUE.resultLevelis updated to1.
- Increment
currentLevelto2. queue=[5, -3].
-
Processing Level 2:
levelSize=2(two nodes at level 2).currentSum=0.- Loop through all nodes at this level (
i = 0 to levelSize-1):- First Iteration (
i = 0):- Dequeue node
5from the queue. - Add
5tocurrentSum:currentSum = 5. - Add left child
3to the queue. - Add right child
2to the queue.
- Dequeue node
- Second Iteration (
i = 1):- Dequeue node
-3from the queue. - Add
-3tocurrentSum:currentSum = 2. - No left child to add.
- Add right child
11to the queue.
- Dequeue node
- First Iteration (
- After processing level 2:
currentSum=2.maxSumremains10because2 < 10.
- Increment
currentLevelto3. queue=[3, 2, 11].
-
Processing Level 3:
levelSize=3(three nodes at level 3).currentSum=0.- Loop through all nodes at this level (
i = 0 to levelSize-1):- First Iteration (
i = 0):- Dequeue node
3from the queue. - Add
3tocurrentSum:currentSum = 3. - Add left child
3to the queue. - Add right child
-2to the queue.
- Dequeue node
- Second Iteration (
i = 1):- Dequeue node
2from the queue. - Add
2tocurrentSum:currentSum = 5. - No left child to add.
- Add right child
1to the queue.
- Dequeue node
- Third Iteration (
i = 2):- Dequeue node
11from the queue. - Add
11tocurrentSum:currentSum = 16. - No left child to add.
- No right child to add.
- Dequeue node
- First Iteration (
- After processing level 3:
currentSum=16.maxSumis updated to16because16 > 10.resultLevelis updated to3.
- Increment
currentLevelto4. queue=[3, -2, 1].
-
Processing Level 4:
levelSize=3(three nodes at level 4).currentSum=0.- Loop through all nodes at this level (
i = 0 to levelSize-1):- First Iteration (
i = 0):- Dequeue node
3from the queue. - Add
3tocurrentSum:currentSum = 3. - No left child to add.
- No right child to add.
- Dequeue node
- Second Iteration (
i = 1):- Dequeue node
-2from the queue. - Add
-2tocurrentSum:currentSum = 1. - No left child to add.
- No right child to add.
- Dequeue node
- Third Iteration (
i = 2):- Dequeue node
1from the queue. - Add
1tocurrentSum:currentSum = 2. - No left child to add.
- No right child to add.
- Dequeue node
- First Iteration (
- After processing level 4:
currentSum=2.maxSumremains16because2 < 16.
- Increment
currentLevelto5. queueis now empty.
-
End of Traversal:
- The queue is empty, which means all levels have been processed.
-
Return Result:
resultLevelis3, which is the level with the maximum sum.- The function returns
3.
Code
Complexity Analysis
Time Complexity
The time complexity of the solution is N is the number of nodes in the binary tree. This is because we perform a level-order traversal (Breadth-First Search) using a queue, which visits each node exactly once.
Space Complexity
The space complexity of the solution is M is the maximum number of nodes at any level in the binary tree. This space is required for the queue that stores the nodes at each level during the traversal. In the worst case (for a complete binary tree), M can be approximately N/2, but it is simplified to
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity